#include <cstdio>
#include <cstdlib>

#define ElemType int
#define ExitNum 9999

typedef struct LNode //单链表
{
    ElemType data;      //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;     // LinkList L;(强调L 是一个链表) <=> LNode *L;(强调L 这一结点)，这两个L是同一个东西。只是为了提高代码的可读性。

//以下函数皆以带头节点的链表实现！！！

//头插法(应用：单链表的逆置) O(n)
LinkList List_HeadInsert(LinkList &L) //逆向建立完整带头结点单链表
{
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next = NULL;                      //初始为空链表
    scanf("%d", &x);                     //输入要插入的值
    while (x != ExitNum)                 //当输入值为 ExitNum 时表示结束
    {
        s = (LNode *)malloc(sizeof(LNode)); //创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;     //将新结点插入表中，L 为头指针
        scanf("%d", &x); //输入下一次要插入的值
    }
    return L;
}

//尾插法 O(n)
LinkList List_TailInsert(LinkList &L) //正向建立完整带头结点单链表
{
    int x;
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    LNode *s, *r = L;                    // r 为表尾指针
    scanf("%d", &x);                     //输入要插入的值
    while (x != ExitNum)                 //当输入值为 ExitNum 时表示结束
    {
        s = (LNode *)malloc(sizeof(LNode)); //创建新结点
        s->data = x;
        r->next = s;
        r = s;           // r 指向新的表尾结点
        scanf("%d", &x); //输入下一次要插入的值
    }
    r->next = NULL; //尾结点指针置空
    return L;
}

//按序号(位序)查找 O(n)
LNode *GetElem(LinkList L, int i) //从第1 个结点出发，顺着指针next域逐个往下搜素，直到找到第i 个结点为止，否则返回最后一结点指针域NULL
{
    int j = 1;          //计数器，初始为1
    LNode *p = L->next; //头结点指针赋值给p
    if (i == 0)         //若 i等于0 ，则返回头结点
        return L;
    if (i < 1) //若i 无效，则返回NULL
        return NULL;
    while (p && j < i) //从第1个结点开始找，查找第i 个结点（若p 为NULL，则退出循环）
    {
        p = p->next;
        j++;
    }
    return p; //返回第i 个结点的指针，若i 大于表长，则返回NULL
}

//按值查找 O(n)
LNode *LocateElem(LinkList L, ElemType e) //从第1 个结点出发，顺着指针next域逐个往下搜素，若某结点data域等于e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL
{
    LNode *p = L->next;               //使p 指向第1 个结点（头结点可看作第0 个结点）
    while (p != NULL && p->data != e) //从第1 个结点开始查找data域为e 的结点
        p = p->next;
    return p; //找到后返回该结点指针，否则返回NULL
}

//按位序插入 O(n)
bool LinkListInsert(LinkList &L, int i, ElemType e) //在单链表L 的第i 个位置插入值为e 的元素
{
    LNode *p = GetElem(L, i - 1); //将p 指向第i-1 个结点
    if (p == NULL)                //若输入的i 不合法，导致指针p 为NULL，则返回false
        return false;
    LNode *s;
    s = (LNode *)malloc(sizeof(LNode)); //创建一个新结点

    //将s 所指结点插入p 所指结点的后方
    s->data = e;
    s->next = p->next;
    p->next = s;

    return true; //插入成功
}

//按位序删除 O(n)
bool LinkListDelete(LinkList &L, int i) //删除单链表L 中第i 个位置的元素
{
    LNode *p = GetElem(L, i - 1); //将p 指向第i-1 个结点
    if (p == NULL)                //若输入的i 不合法，导致指针p 为NULL，则返回false
        return false;

    //将*q 结点从链中"断开"
    LNode *q = p->next;
    p->next = q->next;

    free(q);     //释放*q 结点的存储空间
    return true; //删除成功
}

//求表长 O(n)
int LinkListLength(LinkList L)
{
    LNode *p = L->next;
    int size = 1;
    while (p->next != NULL)
    {
        p = p->next;
        size++;
    }
    return size;
}